package tree;

/**题目：二叉搜索树删除某个节点，然后返回二叉搜索树
 * 二叉搜索树右节点要大于左节点
 * @Author Gavin
 * @date 2022.01.18 22:57
 */
public class tree_19 {
    /**
     * 解题思路：递归
     * 如果目标值大于根节点就递归去右节点删除，否则去左节点删除。
     * 如果等于的话分为三种情况，如果这个节点的左子树为null就返回右子树，如果
     * 右子树为null就返回左子树。如果左右子树都不为null的话，那么找到左子树的最大值节点，
     * 因为要合并删除后的节点，并且二叉搜索树的特点就是右子树要大于左子树。
     * 所以删除节点后就把右子树放到左子树的最大值后面，然后返回左子树就行。
     */
    public TreeNode solution(TreeNode root,int val){
        if(root==null)return null;
        if(val<root.val){
            return solution(root.left,val);
        }else if(val>root.val){
            return solution(root.right,val);
        }else{
            if(root.left==null)return root.right;
            else if(root.right==null)return root.left;

            TreeNode leftMax=root.left;
            //寻找左子树的最大值
            while (leftMax.right!=null)leftMax=leftMax.right;
            leftMax.right=root.right;
            root=root.left;
            return  root;
        }
    }
}
